package com.le.tester.imooc.oldfairy.concurrent;

import org.junit.Assert;
import org.junit.Test;

import java.util.Date;
import java.util.concurrent.atomic.AtomicStampedReference;

/**
 * createTime：2023/6/13 14:42
 * description：无锁并且进步
 */
public class LockFreeStack<T> {

    static class Node<T> {
        Node<T> next;
        T val;

        public Node(T val) {
            this.val = val;
            this.next = null;
        }
    }

    //solve aba api
    //pair 模型，一个值对应一个版本号
    AtomicStampedReference<Node<T>> head;

    public LockFreeStack() {
        Node<T> headNode = new Node<>(null);
        //初始化的索引和版本号
        head = new AtomicStampedReference<>(headNode, 0);
    }

    //push atomic
    public void push(T v) {

        Node<T> newNode = new Node<>(v);

        while (true) {
            int stamp = head.getStamp();
            Node<T> reference = head.getReference();
            //放进队列的尾部
            newNode.next = reference;
            if (head.compareAndSet(reference, newNode, stamp, stamp + 1)) {
                return;
            }
        }
    }


    //pop atomic
    public T pop() {
        while (true) {

            int stamp = head.getStamp();
            Node<T> reference = head.getReference();

            if (reference.next == null) {
                return null;
            }
            Node<T> next = reference.next;
            //对于atomicStampReference,没有版本回退
            head.compareAndSet(reference, next, stamp, stamp + 1);
            return reference.val;
        }


    }


    @Test
    public void testSingle() {
        LockFreeStack<Integer> stack = new LockFreeStack<>();

        for (int i = 0; i < 100; i++) {
            stack.push(i);
        }


        Integer j = null;

        Integer i = 99;

        while ((j = stack.pop()) != null) {
            Assert.assertEquals(j + "", i-- + "");
        }


    }


    @Test
    public void testMultiThreads() throws InterruptedException {
        System.out.println(new Date());

        LockFreeStack<Integer> stack = new LockFreeStack<>();
        for (int i = 0; i < 16; i++) {
            Thread t = new Thread(() -> {
                for (int j = 0; j < 100; j++) {
                    stack.push(j);
                }
            });
            t.start();
            t.join();
        }

        int c = 0;

        while (stack.pop() != null) {
            c++;
        }

        Assert.assertEquals(c + "", "1600");


    }

}
